%------------------------------------------------------------------------------
% File     : DAT056^2 : TPTP v8.2.0. Released v5.4.0.
% Domain   : Data Structures
% Problem  : List operation requiring induction
% Version  : Especial.
% English  :

% Refs     : [Bla12] Blanchette (2012), Email to Geoff Sutcliffe
% Source   : [Bla12]
% Names    : hard.tptp [Bla12]

% Status   : Theorem
% Rating   : 0.70 v8.2.0, 0.85 v8.1.0, 0.82 v7.5.0, 0.86 v7.4.0, 0.78 v7.3.0, 0.89 v7.2.0, 1.00 v7.1.0, 0.88 v7.0.0, 0.86 v6.4.0, 0.83 v6.3.0, 0.80 v6.2.0, 1.00 v5.4.0
% Syntax   : Number of formulae    :   10 (   3 unt;   6 typ;   0 def)
%            Number of atoms       :    3 (   3 equ;   0 cnn)
%            Maximal formula atoms :    1 (   0 avg)
%            Number of connectives :   27 (   0   ~;   0   |;   0   &;  24   @)
%                                         (   0 <=>;   3  =>;   0  <=;   0 <~>)
%            Maximal formula depth :   11 (   5 avg)
%            Number of types       :    3 (   2 usr)
%            Number of type conns  :    5 (   5   >;   0   *;   0   +;   0  <<)
%            Number of symbols     :    5 (   4 usr;   2 con; 0-2 aty)
%            Number of variables   :   10 (   0   ^;  10   !;   0   ?;  10   :)
% SPC      : TH0_THM_EQU_NAR

% Comments :
%------------------------------------------------------------------------------
%----Should-be-implicit typings (2)
thf(ty_n_tc__Foo__Olst_It__J,type,
    lst: $tType ).

thf(ty_n_t_,type,
    a: $tType ).

%----Explicit typings (4)
thf(sy_c_Foo_Oap_001t_,type,
    ap: lst > lst > lst ).

thf(sy_c_Foo_Olst_OCns_001t_,type,
    cns: a > lst > lst ).

thf(sy_c_Foo_Olst_ONl_001t_,type,
    nl: lst ).

thf(sy_v_xs,type,
    xs: lst ).

%----Relevant facts (3)
thf(fact_0_lst_Oinduct,axiom,
    ! [Lst: lst,P: lst > $o] :
      ( ( P @ nl )
     => ( ! [A: a,Lst2: lst] :
            ( ( P @ Lst2 )
           => ( P @ ( cns @ A @ Lst2 ) ) )
       => ( P @ Lst ) ) ) ).

thf(fact_1p_Osimps_I2_J,axiom,
    ! [Ys2: lst,Xs: lst,X: a] :
      ( ( ap @ ( cns @ X @ Xs ) @ Ys2 )
      = ( cns @ X @ ( ap @ Xs @ Ys2 ) ) ) ).

thf(fact_2p_Osimps_I1_J,axiom,
    ! [Ys2: lst] :
      ( ( ap @ nl @ Ys2 )
      = Ys2 ) ).

%----Conjectures (1)
thf(conj_0,conjecture,
    ! [Ys: lst,Zs: lst] :
      ( ( ap @ xs @ ( ap @ Ys @ Zs ) )
      = ( ap @ ( ap @ xs @ Ys ) @ Zs ) ) ).

%------------------------------------------------------------------------------